﻿using System;
using UnityEngine;

namespace PathFind.Algo {
    public struct Coordinate {
        public override bool Equals(object obj) {
            return obj is Coordinate other && Equals(other);
        }

        public override int GetHashCode() {
            unchecked {
                return (x.GetHashCode() * 397) ^ y.GetHashCode();
            }
        }

        public short x, y;

        public Coordinate(short x, short y) {
            this.x = x;
            this.y = y;
        }

        //定义委托
        public delegate float DistFuncType(Coordinate co1, Coordinate co2);

        public static DistFuncType CurDistFunc = SqrtDist;


        public static DistFuncType[] DistFuncMap = {
            SqrtDist,
            ManhattanDist,
            OctileDist,
            ChebyshevDist,
        };

        // 1. Euclidean distance: 性能不行
        public static float SqrtDist(Coordinate co1, Coordinate co2) {
            int absX = Mathf.Abs(co1.x - co2.x);
            int absY = Mathf.Abs(co1.y - co2.y);
            // http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#euclidean-distance-squared
            return Mathf.Sqrt(absX * absX + absY * absY);
        }

        // 2. Manhattan:路径不真实,适用于四方向移动的格子地图
        public static float ManhattanDist(Coordinate co1, Coordinate co2) {
            int absX = Mathf.Abs(co1.x - co2.x);
            int absY = Mathf.Abs(co1.y - co2.y);
            // 可以再乘以一个反映格子到格子之间移动消耗的值D,
            // 为了最优路径,可以选择D为格子到格子间的最小消耗
            // 也有越接近终点,h的D越小,g的D越大
            return absX + absY;
        }

        // 3. Octile(考虑了对角线距离的移动,)
        public static float OctileDist(Coordinate co1, Coordinate co2) {
            int absX = Mathf.Abs(co1.x - co2.x);
            int absY = Mathf.Abs(co1.y - co2.y);
            return (absX + absY) + (SqrtOfTwo - 2) * Mathf.Min(absX, absY);
            // 通用的, D是水平或垂直方向移动的距离, D2表示对角线移动的距离
            // 当D=1,D2=1.414(即根号2)时,称为 Octile 距离
            // return D * (absX + absY) + (D2 - 2 * D) * Mathf.Min(absX, absY);
        }

        // 4. Chebyshev
        public static float ChebyshevDist(Coordinate co1, Coordinate co2) {
            int absX = Mathf.Abs(co1.x - co2.x);
            int absY = Mathf.Abs(co1.y - co2.y);
            // D=1,D2=1时,称为 Chebyshev 距离
            return (absX + absY) - Mathf.Min(absX, absY);
        }

        private static readonly float SqrtOfTwo = Mathf.Sqrt(2.0f);

        public float CallDistFunc(Coordinate rhs) {
            return CurDistFunc(this, rhs);

            // 5. 格子寻路最通用的公式是:
            // D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
            // When D = 1 and D2 = 1, this is called the Chebyshev distance.
            // When D = 1 and D2 = sqrt(2), this is called the octile distance.

            // 6.通用公式(4)的另一种形式是:
            // D * max(dx, dy) + (D2-D) * min(dx, dy).
            // int diagDist = Mathf.Min(absX, absY);
            // return Mathf.Max(absX, absY) + diagDist;
            // int straightDist = Mathf.Max(absX, absY) - diagDist;
            // return diagDist * 1.414213562373095f + straightDist;

            // 7.骚操作:
            // 给h加一个代表叉乘的分量,这样越直的路径会越容易得到,适合用来解决有大量最优路径的情况(call it ties)!
            // dx1 = current.x - goal.x
            // dy1 = current.y - goal.y
            // dx2 = start.x - goal.x
            // dy2 = start.y - goal.y
            // cross = abs(dx1*dy2 - dx2*dy1)
            // heuristic += cross*0.001
            // 8.解决ties的另一个方法:使值相同的节点,在优先级队列里是先入先出/先入后出的!
        }

        public void Add(Coordinate rhs) {
            x += rhs.x;
            y += rhs.y;
        }

        public static Coordinate operator +(Coordinate a, Coordinate b) {
            Coordinate c;
            c.x = (short) (a.x + b.x);
            c.y = (short) (a.y + b.y);
            return c;
        }

        public static Coordinate operator -(Coordinate a, Coordinate b) {
            Coordinate c;
            c.x = (short) (a.x - b.x);
            c.y = (short) (a.y - b.y);
            return c;
        }

        public static bool operator ==(Coordinate a, Coordinate b) {
            return a.x == b.x && a.y == b.y;
        }

        public static bool operator !=(Coordinate a, Coordinate b) {
            return !(a == b);
        }

        public bool Equals(Coordinate other) {
            return x == other.x && y == other.y;
        }

        public bool IsEquals(int posX, int posY) {
            return x == posX && y == posY;
        }

        public override string ToString() {
            return $"({x},{y})";
        }

        public static Coordinate[] DrawLine(short startX, short startY, short endX, short endY) {
            return new[] {
                new Coordinate(startX, startY),
                new Coordinate(endX, endY),
            };
        }
    }
}